public class Solution96 {

    int[] dp;

    public int numTrees(int n) {
        dp = new int[n + 1];
        dp[0] = 1;
        return dfs(n);
    }

    private int dfs(int n) {
        if (dp[n] != 0) {
            return dp[n];
        }
        for (int i = 0; i < n; i++) {
            dp[n] += dfs(i) * dfs(n - i - 1);
        }
        return dp[n];
    }
}
